class Solution {
public:
    int jump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    	if (n <= 1) {
			return 0;
		}

		vector<int> step(n, - 1);
		step[0] = 0;
		int cur = 0;
		for (int i = 0; i < n; ++i) {
			if (step[i] < 0) {
				break;
			}
			if (A[i] + i > cur) {
				for (int j = cur + 1; j < n && j <= A[i] + i; ++j) {
					step[j] = step[i] + 1;
				}
				cur = A[i] + i;
			}
		}
        return step[n - 1];
    }
};